package org.deng.learn.basic.sort;

/**
 * @author DengLibin
 * @Description 归并排序（分治策略）
 * @Date 2018/11/6 0006 14:09
 */
public class MergeSort extends Sort {

    public  static  void main(String[] args){

        int[] arr = {5,6,234,34,23,23};

       // merge(arr, arr.length /2,0,3,temp);
        mergeSort(arr,0,arr.length - 1);
        showArr(arr);

    }

    public static void mergeSort(int[] arr, int start, int end){
        if (start < end)
        {
            int middle = (start + end) / 2;
            mergeSort(arr, start, middle);
            mergeSort(arr, middle + 1, end);
            merge(arr, middle, start,end);
        }
    }


    //合并(左边和右边已经排好序了)
    public static void  merge(int[] arr, int middle,  int sIndex, int eIndex ){
        int[] temp = new int[eIndex - sIndex +1];
        int a = sIndex;
        int b = middle+1;
        int start = 0;
        while (a <= middle && b <= eIndex){
            if(arr[a] < arr[b]){
                temp[start++] = arr[a++];
            }else{
                temp[start++] = arr[b++];
            }
        }
        while (a <= middle){
            temp[start++] = arr[a++];
        }
        while (b <= eIndex){
            temp[start++] = arr[b++];
        }
        //将temp中的元素全部拷贝到原数组中
        for (int i = 0; i < start; i++)
        {
            arr[sIndex + i] = temp[i];
        }

    }
}
